/**
 * 707. 设计链表
 * https://leetcode-cn.com/problems/design-linked-list/
 */
public class Solutions_707 {
    public static void main(String[] args) {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addAtHead(1);  // {1}
        linkedList.deleteAtIndex(0);  // {}

//        MyLinkedList linkedList = new MyLinkedList();
//        linkedList.addAtHead(7);  // {7}
//        linkedList.addAtHead(2);  // {2, 7}
//        linkedList.addAtHead(1);  // {1, 2, 7}
//        linkedList.addAtIndex(3,0);  // {1, 2, 7, 0}
//        linkedList.deleteAtIndex(2);  // {1, 2, 0}
//        linkedList.addAtHead(6);  // {6, 1, 2, 0}
//        linkedList.addAtTail(4);  // {6, 1, 2, 0, 4}
//        int res1 = linkedList.get(4);  // {4}
//        System.out.println(res1);
//        linkedList.addAtHead(4);  // {4, 6, 1, 2, 0}
//        linkedList.addAtIndex(5,0);  // {4, 6, 1, 2, 0, 5}
//        linkedList.addAtHead(6);  // {6, 4, 6, 1, 2, 0, 5}
    }
}

/**
 * 解法一：双向链表实现（9ms）
 */
class MyLinkedList {
    DoubleListNode dummyHead = null, dummyTail = null;
    int size = 0;

    public MyLinkedList() {
        // 建立虚拟头尾结点，并建立联系
        dummyHead = new DoubleListNode();
        dummyTail = new DoubleListNode();
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            // 索引无效
            return -1;
        }
        DoubleListNode node = getNode(index);
        return node.val;
    }

    /**
     * 获取 index 索引上的结点对象
     */
    public DoubleListNode getNode(int index) {
        DoubleListNode cur = dummyHead;
        int mid = size / 2;
        if (index < mid) {
            // 从前往后找，通过后继结点
            for (int i = -1; i < index; i++) {
                cur = cur.next;
            }
        } else {
            cur = dummyTail;
            // 从后往前找，通过前驱结点
            for (int i = size; i > index; i--) {
                cur = cur.prev;
            }
        }
        return cur;
    }

    public void addAtHead(int val) {
        // 在 head 与 head.next 结点中插入结点
        DoubleListNode newHead = new DoubleListNode(val, dummyHead, dummyHead.next);
        dummyHead.next.prev = newHead;
        dummyHead.next = newHead;
        // 结点插入成功，链表长度加 1
        ++ size;
    }

    public void addAtTail(int val) {
        DoubleListNode newTail = new DoubleListNode(val, dummyTail.prev, dummyTail);
        dummyTail.prev.next = newTail;
        dummyTail.prev = newTail;
        // 结点插入成功，链表长度加 1
        ++ size;
    }

    public void addAtIndex(int index, int val) {
        if (index < 0) {
            // 插入到头结点
            addAtHead(val);
            return;
        } else if (index > size) {
            // 大于链表长度
            return;
        } else if (index == size) {
            // 插入到尾结点
            addAtTail(val);
            return;
        }
        // 获取 index - 1 索引上的结点
        DoubleListNode preNode = getNode(index - 1);
        DoubleListNode newNode = new DoubleListNode(val, preNode, preNode.next);
        // 在 preNode 与 preNode.next 中插入结点
        preNode.next.prev = newNode;
        preNode.next = newNode;
        // 结点插入成功，链表长度加 1
        ++ size;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            // 索引无效
            return;
        }
        // 获取 index 索引上的结点
        DoubleListNode curNode = getNode(index);
        // 双向链表删除结点：要删除结点的前驱结点的后继结点，指向要删除结点的后继结点
        // 要删除结点的后继结点的前驱结点，指向要删除的前驱结点
        curNode.next.prev = curNode.prev;
        curNode.prev.next = curNode.next;
        // 结点删除成功，链表长度减 1
        -- size;
    }

}


/**
 * 解法一：单向链表实现（13ms）
 */
class MyLinkedList2 {
    ListNode head;
    int size;

    /** Initialize your data structure here. */
    public MyLinkedList2() {
        size = 0;
        head = new ListNode(-1);
    }

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode res = getNode(index);
        return res == null ? -1 : res.val;
    }

    /**
     * 获取 index 索引上的结点对象
     */
    public ListNode getNode(int index) {
        ListNode cur = head;
        for (int i = -1; i < index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        ListNode newNode = new ListNode(val);
        // 在 head 与 head.next 结点中插入结点
        newNode.next = head.next;
        head.next = newNode;
        // 结点插入成功，链表长度加 1
        ++ size;
    }

    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        ListNode newNode = new ListNode(val);
        // 获取当前链表的最后一个元素
        ListNode tail = getNode(size - 1);
        tail.next = newNode;
        // 结点插入成功，链表长度加 1
        ++ size;
    }

    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        if (index > size) {
            // 大于链表长度
            return;
        } else if (index <= 0) {
            // 插入到头结点
            addAtHead(val);
            return;
        }
        // 获取 index - 1 位置上的结点
        ListNode preNode = getNode(index - 1);
        ListNode newNode = new ListNode(val);
        // 在 preNode 与 preNode.next 中插入结点
        newNode.next = preNode.next;
        preNode.next = newNode;
        // 结点插入成功，链表长度加 1
        ++ size;
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            // 索引无效
            return;
        }
        // 获取要删除结点的前驱结点，即 index - 1 索引上的结点
        ListNode preNode = getNode(index - 1);
        // 删除：要删除结点的前驱结点的后继结点，指向要删除结点的后继结点
        preNode.next = preNode.next.next;
        // 结点删除成功，链表长度减 1
        -- size;
    }
}
